目標：
選這題的目標旨在說明更為典型的動態規劃算法。

原題：

Question:
You are climbing a staircase. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.

Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

分析/解題：
題目描述有一個要爬n階才能到頂端的階梯，每次只能爬1階或2階，
試求有多少種不同的方法可以走到頂端。
如果以窮舉的話我們可能需要列很久，
所以這時候又回到了看看是否能找出相互關係的時候了。

我們考慮要爬n階的話，首先要先爬到n-1階或n-2階，
因為只有一次走1階或一次走2階的選擇。
也就是說，走到n階的方法，就相當於走到n-1階的方法和走到n-2階的方法和。
因為最後的步伐已經固定了，
我們同時還可以保證這兩個方法的組合之間不會互相重複
(一個最後走1步，一個最後走2步)。

我們可以選擇開一個res的陣列，初始化前2階以後，
一路加上去最終得到到第n階的方法數，下面Java的版本因為陣列由0開始，
有刻意將數字不先行化簡，讀者應該可以很簡單地對照。

Java:

class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        int[] res = new int[n];
        res[1-1] = 1;
        res[2-1] = 2;
        for(int i = 3; i <= n; i++) {
            res[i-1] = res[i-1-1] + res[i-2-1];
        }
        return res[n-1];
    }
}

Python的部分，則採用兩個數s1, s2來輪替使用，可以節省記憶體。
每次應該要做的，是將s1+s2的值擺到s2，而將s2的值擺到s1的位置。
(等於把兩個數代表的位置遞移了一層)
(Java也可以用類似的作法，但需要多宣告一個暫存值進行儲存)

Python:

class Solution:
    def climbStairs(self, n: 'int') -> 'int':
        if n == 1:
            return 1
        if n == 2:
            return 2        
        s1, s2 = 1, 2
        for _ in range(n - 2):
            s1, s2 = s2, s1 + s2
        return s2

面試實際可能會遇到的問題：
「時間/空間複雜度？」
（O(N), 依方法而定，
上面Java的寫法需要O(N)，Python的寫法則只需O(1)）

「哪個寫法比較好？」
(以空間節省的角度來說是Python版本的寫法較佳，
但如果我們不止需要算一次的話，執行一次n階，
其實可以將n階以下的走法數量全部記起來，
這樣被讀取的時候可以先查是否可以直接拿結果回傳，
所以反覆執行的效率會變比較好，不過這個就需要再修改一下程式就是了)

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0083. Remove Duplicates from Sorted List (Easy)